package shenxingfu.d20211103.t2;

import java.util.Stack;

/**
 * @author habitplus
 * @since 2021-11-03 19:48
 */
public class Main {

    public int[] max_sub_matrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[]{0, -1, -1, -1, -1};
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int max = Integer.MIN_VALUE;
        int cur = 0;
        int[] t;
        for (int i = 0; i < n; i++) {
            t = new int[m];
            for (int j = i; j < n; j++) {
                cur = 0;
                for (int k = 0; k < m; k++) {
                    t[k] += matrix[j][k];
                    cur += t[k];
                    max = Math.max(max, cur);
                    cur = Math.max(cur, 0);
                }
            }
        }

        return new int[3];
    }

    public String dec(String str, int up_chr_offset, int low_chr_offset) {
        if (str == null || str.length() < 1) return "";
        char[] chs = str.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] != ' ' && chs[i] != '"') {
                if (chs[i] - up_chr_offset >= 'A' && chs[i] - up_chr_offset <= 'Z') {
                    chs[i] = (char) (chs[i] + up_chr_offset);
                } else if (chs[i] - low_chr_offset >= 'a' && chs[i] - low_chr_offset <= 'z') {
                    chs[i] = (char) (chs[i] + low_chr_offset);
                }
            }
        }

        return new String(chs);
    }

    static class Node {
        char ch;
        int cnt;

        public Node(char ch, int cnt) {
            this.ch = ch;
            this.cnt = cnt;
        }
    }

    public String get_substr(String s) {
        if (s == null || s.length() < 1) return "";

        char[] chs = s.toCharArray();
        int n = chs.length;
        Stack<Node> stack = new Stack<>();

        int i = 0;
        while (i < n) {
            if (stack.isEmpty()) {
                stack.push(new Node(chs[i], 1));
                i++;
            } else if (stack.peek().ch == chs[i]) {
                stack.peek().cnt++;
                i++;
            } else {
                // stack 不为空 && stack.peek().ch != chs[i]
                while (!stack.isEmpty() && stack.peek().cnt > 2) {
                    stack.pop();
                }
                // stack 为空，直接下一个循环
                // stack不为空：
                //      1. stack.peek().ch == chs[i]，直接下一次循环
                //      2. stack.peek().ch != chs[i]，当前字符进栈
                if (!stack.isEmpty() && stack.peek().ch != chs[i]) {
                    stack.push(new Node(chs[i], 1));
                    i++;
                }
            }
        }

        if (!stack.isEmpty() && stack.peek().cnt > 2) {
            stack.pop();
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            for (int j = 0; j < node.cnt; j++) {
                sb.append(node.ch);
            }
        }

        return sb.reverse().toString();
    }


}
